The search for a data structure that supports $O(1)$ modification led us to shift complexity from physical element shifting to managing relationships. This concept is fundamentally realized in the Linked List, where the logical order is maintained entirely through explicit references (pointers) rather than physical memory contiguity.
- A Linked List is a sequential collection of dynamically allocated elements called nodes. The sequence's order is determined by each node storing a pointer to the subsequent node.
- Node: The fundamental unit, defined by the structure: {item, next}.
- Head Pointer: A dedicated pointer that points to the first node in the list. If the list is empty, the Head pointer is set to NULL.
- Tail/Termination: The `next` pointer of the last node is always set to NULL, marking the end of the sequence.
- This design allows the structure to grow dynamically and permits modification (insertion/deletion) in $O(1)$ time, provided we are already positioned at the insertion point $i$.
Key Characteristics
Unlike Arrays, Linked Lists do not require contiguous memory blocks. This flexibility is achieved by sacrificing $O(1)$ random access for superior performance in dynamic operations:
| Characteristic | Array | Linked List |
|---|---|---|
| Memory Allocation | Contiguous | Non-contiguous |
| Random Access | $O(1)$ | $O(n)$ (Traversal) |
| Insertion at Head | $O(n)$ | $O(1)$ |